<!doctype html>
<html lang="zh-cn">
<head>

    <meta charset="utf-8">
    <meta name="generator" content="Hugo 0.57.2" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1">

    <title>数据结构与算法--树 | The Sky of OtsWang</title>
    <meta property="og:title" content="数据结构与算法--树 - The Sky of OtsWang">
    <meta property="og:type" content="article">
        
    <meta property="article:published_time" content="2019-05-24T18:51:58&#43;08:00">
        
        
    <meta property="article:modified_time" content="2019-05-24T18:51:58&#43;08:00">
        
    <meta name="Keywords" content="golang,go语言,otswang,java,博客,python">
    <meta name="description" content="数据结构与算法--树">
        
    <meta name="author" content="OtsWang">
    <meta property="og:url" content="https://otswang.gitee.io/hugo/post/algorithm/tree/">
    <link rel="shortcut icon" href="/favicon.ico" type="image/x-icon">

    <link rel="stylesheet" href="/hugo/css/normalize.css">
    
        <link rel="stylesheet" href="/hugo/css/prism.css">
    
    <link rel="stylesheet" href="/hugo/css/style.css">
    <script type="text/javascript" src="//cdn.bootcss.com/jquery/3.2.1/jquery.min.js"></script>

    


    
    
</head>

<body>
<header id="header" class="clearfix">
    <div class="container">
        <div class="col-group">
            <div class="site-name ">
                
                    <a id="logo" href="https://otswang.gitee.io/hugo/">
                        The Sky of OtsWang
                    </a>
                
                <p class="description">擅长写HelloWorld的小小码农</p>
            </div>
            <div>
                <nav id="nav-menu" class="clearfix">
                    
                    
                    <a  href="https://otswang.gitee.io/hugo/" title="Home">Home</a>
                    
                    <a  href="https://otswang.gitee.io/hugo/tags/" title="Tags">Tags</a>
                    
                    <a  href="https://otswang.gitee.io/hugo/categories/" title="Categories">Categories</a>
                    
                    <a  href="https://otswang.gitee.io/hugo/archives/" title="Archives">Archives</a>
                    
                    <a  href="https://otswang.gitee.io/hugo/about/" title="About">About</a>
                    
                </nav>
            </div>
        </div>
    </div>
</header>


<div id="body">
    <div class="container">
        <div class="col-group">

            <div class="col-8" id="main">
                <div class="res-cons">
                    <article class="post">
                        <header>
                            <h1 class="post-title">数据结构与算法--树</h1>
                        </header>
                        <date class="post-meta meta-date">
                            2019年5月24日
                        </date>
                        
                        <div class="post-meta">
                            <span>|</span>
                            
                                <span class="meta-category"><a href="https://otswang.gitee.io/hugo/categories/algorithm">Algorithm</a></span>
                            
                        </div>
                        
                        
                        
                        <div class="post-content">
                            <p>树是基本又复杂的数据结构</p>

<h2 id="二叉树">二叉树</h2>

<p><img src="https://s2.ax1x.com/2019/05/24/VFKhcQ.jpg" alt="二叉树" /></p>

<p>二叉树又分为满二叉树和完全二叉树。完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。</p>

<p>性质：</p>

<ol>
<li>非空二叉树中，第i层的节点总数不超过 2^(i-1).</li>
<li>深度为h的二叉树，最多有2^h - 1 个节点</li>
<li>对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;</li>
<li>具有n个结点的完全二叉树的深度为log2(n+1);</li>
</ol>

<h2 id="二叉查找树">二叉查找树</h2>

<p>左子树小于根结点，右子树大于根结点。进行中序遍历，即可获得有序的数列。插入和查找的时间复杂度为O(logn)，</p>
                        </div>

                        


                        


                        <div class="post-meta meta-tags">
                            
                            <ul class="clearfix">
                                
                                <li><a href="https://otswang.gitee.io/hugo/tags/%E7%AE%97%E6%B3%95">算法</a></li>
                                
                            </ul>
                            
                        </div>
                    </article>
                    
    

    
    
                </div>
            </div>
            <div id="secondary">

    <section class="widget">
        <form id="search" action="//www.google.com/search" method="get" accept-charset="utf-8" target="_blank" _lpchecked="1">
      
      <input type="text" name="q" maxlength="20" placeholder="Search">
      <input type="hidden" name="sitesearch" value="https://otswang.gitee.io/hugo/">
      <button type="submit" class="submit icon-search"></button>
</form>
    </section>

    
    <div class="clear">
        <div class="toc-article">
            <div class="toc-title">文章目录</dixsv>
            <nav id="TableOfContents">
<ul>
<li>
<ul>
<li><a href="#二叉树">二叉树</a></li>
<li><a href="#二叉查找树">二叉查找树</a></li>
</ul></li>
</ul>
</nav>
        </div>
    </div>
    

</div>
        </div>
    </div>
</div>
<footer id="footer">
    <div class="container">
        &copy; 2020 <a href="https://otswang.gitee.io/hugo/">The Sky of OtsWang By OtsWang</a>.
        Powered by <a rel="nofollow noreferer noopener" href="https://gohugo.io" target="_blank">Hugo</a>.
        <a href="https://www.flysnow.org/" target="_blank">Theme</a> based on <a href="https://github.com/Dudiao137/maupassant-hugo" target="_blank">maupassant-ots</a>.
        
    </div>
</footer>


    <script type="text/javascript">
    
    (function(){
        $("pre code").parent().addClass("line-numbers")
    }())

    window.MathJax = {
        tex2jax: {
            inlineMath: [ ['$','$'] ],
            processEscapes: true
        }
    };
    </script>
    <script type="text/javascript" src="/hugo/js/prism.js" async="true"></script>
    <script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML' async></script>

<a id="rocket" href="#top"></a>
<script type="text/javascript" src="/hugo/js/totop.js?v=0.0.0" async=""></script>







 
 <script src="https://mermaidjs.github.io/scripts/mermaid.min.js"></script>
 <script>
       mermaid.initialize({ startOnLoad: true });
 </script>
</body>
</html>
